package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/1 0001.
 */
public class Spiral_Matrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        int curDir = 0;
        List<Integer> rst = new LinkedList<Integer>();
        if(matrix==null || matrix.length==0)
            return rst;
        int m = matrix.length;
        int n = matrix[0].length;
        int totalNum = m*n;
        if(m<=1){
            for(int j = 0;j<n;j++)
                rst.add(matrix[0][j]);
            return rst;
        }
        else if(n<=1){
            for (int[] aMatrix : matrix) {
                rst.add(aMatrix[0]);
            }
            return rst;
        }

        int[] fourConer = new int[4];
        fourConer[0]  = n-1;
        fourConer[1] = m-1;
        fourConer[2] = 0;
        fourConer[3] = 0;
        int count = 0;
        int i;
        int beginx = 0;
        int beginy = 0;
        while(count<totalNum){
            if(curDir==0){
                if(beginx==beginy && count==totalNum-1){
                    rst.add(matrix[beginx][beginy]);
                    break;
                }
                for(i=beginy;i<fourConer[curDir];i++){
                    rst.add(matrix[beginx][i]);
                    count++;

                }
                beginy = i;
                fourConer[curDir] = i-1;
            }
            if(curDir==1){
                for(i=beginx;i<fourConer[curDir];i++){
                    rst.add(matrix[i][beginy]);
                    count++;

                }
                beginx = i;
                fourConer[curDir] = i-1;
            }
            if(curDir==2){
                for(i=beginy;i>fourConer[curDir];i--){
                    rst.add(matrix[beginx][i]);
                    count++;

                }
                beginy = i;
                fourConer[curDir] = i+1;
            }
            if(curDir==3){
                for(i=beginx;i>fourConer[curDir];i--){
                    rst.add(matrix[i][beginy]);
                    count++;

                }
                beginx = i+1;
                beginy++;
                fourConer[curDir] = i+1;

            }
            curDir = (curDir+1)%4;
        }
        return rst;
    }

    public static void main(String[] args){
        Spiral_Matrix spiral_matrix = new Spiral_Matrix();
        int[][] matrix = {{1,2},{1,2},{1,3}};
        System.out.println(spiral_matrix.spiralOrder(matrix));
    }
}
